package online.longzipeng;

/**
 * @author lzp
 * @Date:2023/10/13
 * @description: 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 * <p>
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * <p>
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 */
public class Solution86 {

	/**
	 * 直接用两个链表，一个存小于3的一个存大于等于3的，遍历完成后连接两个链表， 时间复杂度 O(n)
	 */
	public static ListNode partition(ListNode head, int x) {
		ListNode res = new ListNode(-1);
		ListNode cur = new ListNode(-1);
		ListNode resPre = res;
		ListNode curPre = cur;
		while (head != null) {
			if (head.val < x) {
				resPre.next = new ListNode(head.val);
				resPre = resPre.next;
			} else {
				curPre.next = new ListNode(head.val);
				curPre = curPre.next;
			}
			head = head.next;
		}
		resPre.next = cur.next;
		return res.next;
	}

	public static void main(String[] args) {
//		online.longzipeng.ListNode list1 = new online.longzipeng.ListNode(1, 4, 3, 2, 5, 2);
		ListNode list1 = new ListNode(2, 1);
		PrintUtils.printListNode(partition(list1, 2));
	}
}
